package com.lwl.Algorithmic_data_structure.class19暴力递归2动态规划;

/**
 * @author lwl
 * @Description 给两个一维数组，分别代表货物的价值和重量，一个一个容量w的背包，请你求出可以带走的最大价值
 * @date 2023/6/7 17:41
 */
public class Code01Bag01 {

    public static void main(String[] args) {
        int[] weights = {3, 2, 4, 7, 3, 1, 7};
        int[] values = {5, 6, 3, 19, 12, 4, 2};
        int bag = 15;
        System.out.println(getMaxValue(weights, values, bag));
        System.out.println(getMaxValue2(weights, values, bag));
        System.out.println(getMaxValue3(weights, values, bag));
    }

    static private int getMaxValue3(int[] weight, int[] value, int bagSize) {
        int n = weight.length;
        int[][] dp = new int[n + 1][bagSize + 1];
        // 超出选择范围都是0，base case
        for (int i = 0; i <= bagSize; i++) {
            dp[n][i] = 0;
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = weight[i]; j <= bagSize; j++) {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j - weight[i]] + value[i]);
            }
        }
        return dp[0][bagSize];
    }

    static private int getMaxValue2(int[] weight, int[] value, int bagSize) {
        int[][] cache = new int[weight.length][bagSize + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int j = 0; j < bagSize + 1; j++) {
                cache[i][j] = -1;
            }
        }
        return process2(weight, value, bagSize, 0, cache);
    }

    // index : 0 ~ N + 1
    // bagSize : 0 ~ bagSize
    private static int process2(int[] weight, int[] value, int bagSize, int index, int[][] cache) {
        if (index == weight.length) {
            return 0;
        }
        if (cache[index][bagSize] != -1) {
            return cache[index][bagSize];
        }
        // 带走
        int take = 0;
        if (bagSize - weight[index] >= 0) {
            take = process2(weight, value, bagSize - weight[index], index + 1, cache) + value[index];
        }
        // 不带走
        int notTake = process2(weight, value, bagSize, index + 1, cache);
        cache[index][bagSize] = Math.max(take, notTake);
        return cache[index][bagSize];
    }

    static private int getMaxValue(int[] weight, int[] value, int bagSize) {
        return process(weight, value, bagSize, 0);
    }

    private static int process(int[] weight, int[] value, int bagSize, int index) {
        if (index == weight.length) {
            return 0;
        }
        // 带走
        int take = 0;
        if (bagSize - weight[index] >= 0) {
            take = process(weight, value, bagSize - weight[index], index + 1) + value[index];
        }
        // 不带走
        int notTake = process(weight, value, bagSize, index + 1);
        return Math.max(take, notTake);
    }

}
